package com.wayne.leetcode.problems;

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution1475 {
  public static int[] finalPrices(int[] prices) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < prices.length; i++) {
      while (!stack.isEmpty() && prices[i] <= prices[stack.peek()]) {
        Integer pre = stack.pop();
        prices[pre] = prices[pre] - prices[i];
      }
      stack.push(i);
    }
    return prices;
  }

  public static void main(String[] args) {
    finalPrices(new int[]{8, 4, 6, 2, 3});
  }
}